package leetcode.editor.cn.q1_300.q200;
//编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性： 
//
// 
// 每行的元素从左到右升序排列。 
// 每列的元素从上到下升序排列。 
// 
//
// 
//
// 示例 1： 
// 
// 
//输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
//输出：true
// 
//
// 示例 2： 
// 
// 
//输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21
//,23,26,30]], target = 20
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= n, m <= 300 
// -10⁹ <= matrix[i][j] <= 10⁹ 
// 每行的所有元素从左到右升序排列 
// 每列的所有元素从上到下升序排列 
// -10⁹ <= target <= 10⁹ 
// 
//
// 👍 1292 👎 0

import leetcode.editor.cn.util.arr.ArrayUtil;

/**
 * 先向前找，直到找到比 target 大的，然后从这个大的下一行开始向后找，找到比 target 小的
 * 直到找到 target
 */
public class Q240_SearchA2dMatrixIi {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int m = matrix.length;
            int n = matrix[0].length;
            int row = 0;
            int col = 0;

            // 向前找
            for (int i = 0; i < n; i++) {
                col = i;
                if (target == matrix[0][i]) {
                    return true;
                } else if (target < matrix[0][i]) {
                    break;
                }
            }

            // 向后找
            while (true) {
                row++;
                if (row == m || col < 0) {
                    break;
                }
                if (target == matrix[row][col]) {
                    return true;
                } else if (target < matrix[row][col]) {
                    while (col >= 0) {
                        if (target == matrix[row][col]) {
                            return true;
                        } else if (target < matrix[row][col]) {
                            col--;
                        } else {
                            break;
                        }
                    }
                }
            }

            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q240_SearchA2dMatrixIi().new Solution();
        // TO TEST
        int[][] arr = (int[][]) ArrayUtil.genArrayByString(" [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]");
        System.out.println(solution.searchMatrix(arr, 0));
        System.out.println(solution.searchMatrix(arr, 5));
        System.out.println(solution.searchMatrix(arr, 20));
    }
}